Noson S. Yanofsky, "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points"
Abstrakt
Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.
紹介文
Introduciton
Lawvereの論文では，いくつかの対角線補題/古典的パラドクス/不完全性定理が圏論的な流儀で説明されている 次の例を与えている
この方向性での研究は↓を参照．
Lawvereの成果を圏論の言葉なしで説明することを目標とする． 集合と関数の概念を使う．
Cantorの定理
自然数の集合$ \Nについて
$ \N \to \mathbf{2}^\Nへの全射は存在しない．
ここで$ \mathbf{2} = \{0,1\}とし，$ \bf{2}^\Nは$ \N \to \bf{2}への関数の集合とする．
Cantorの定理の一般化1
任意の集合$ Tについて
$ T \to \mathbf{2}^Tへの全射は存在しない．
remark:
$ \bf 2,3,\dotsのときは正しいが
$ \mathbf{1} = \{0\}のときは正しくない．存在する．
Cantorの定理の一般化2
任意の集合$ Tについて
$ T \to Y^Tへの全射は存在しない．
$ Yはnon-degenerate（非退化な?）集合
non-degenerateが意味するのは，
$ Yの要素は置き換え可能である．
不動点を持たない（$ \alpha(y) = yとなるような$ y \in Yが存在しない）$ \alphaが存在する．